{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Put Boxes Into the Warehouse I"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxBoxesInWarehouse"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #把箱子放进仓库里 I"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定两个正整数数组&nbsp;<code>boxes</code>&nbsp;和&nbsp;<code>warehouse</code>&nbsp;，分别包含单位宽度的箱子的高度，以及仓库中 <code>n</code> 个房间各自的高度。仓库的房间分别从&nbsp;<code>0</code>&nbsp;到&nbsp;<code>n - 1</code>&nbsp;自左向右编号，&nbsp;<code>warehouse[i]</code>&nbsp;（索引从 0 开始）是第&nbsp;<code>i</code>&nbsp;个房间的高度。</p>\n",
    "\n",
    "<p>箱子放进仓库时遵循下列规则：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>箱子不可叠放。</li>\n",
    "\t<li>你可以重新调整箱子的顺序。</li>\n",
    "\t<li>箱子只能从左向右推进仓库中。</li>\n",
    "\t<li>如果仓库中某房间的高度小于某箱子的高度，则这个箱子和之后的箱子都会停在这个房间的前面。</li>\n",
    "</ul>\n",
    "\n",
    "<p>你最多可以在仓库中放进多少个箱子？</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/08/26/11.png\" style=\"height: 242px; width: 400px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>boxes = [4,3,4,1], warehouse = [5,3,3,4,1]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：\n",
    "</strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/08/26/12.png\" style=\"height: 242px; width: 280px;\" />\n",
    "我们可以先把高度为 1 的箱子放入 4 号房间，然后再把高度为 3 的箱子放入 1 号、 2 号或 3 号房间，最后再把高度为 4 的箱子放入 0 号房间。\n",
    "我们不可能把所有 4 个箱子全部放进仓库里。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/08/26/21.png\" style=\"height: 202px; width: 400px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>boxes = [1,2,2,3,4], warehouse = [3,4,1,2]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/08/26/22.png\" style=\"height: 202px; width: 280px;\" />\n",
    "</strong>我们注意到，不可能把高度为 4 的箱子放入仓库中，因为它不能通过高度为 3 的房间。\n",
    "而且，对于最后两个房间 2 号和 3 号来说，只有高度为 1 的箱子可以放进去。\n",
    "我们最多可以放进 3 个箱子，如上图所示。黄色的箱子也可以放入 2 号房间。\n",
    "交换橙色和绿色箱子的位置，或是将这两个箱子与红色箱子交换位置，也是可以的。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>boxes = [1,2,3], warehouse = [1,2,3,4]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>由于第一个房间的高度为 1，我们只能放进高度为 1 的箱子。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == warehouse.length</code></li>\n",
    "\t<li><code>1 &lt;= boxes.length, warehouse.length &lt;= 10^5</code></li>\n",
    "\t<li><code>1 &lt;= boxes[i], warehouse[i] &lt;= 10^9</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [put-boxes-into-the-warehouse-i](https://leetcode.cn/problems/put-boxes-into-the-warehouse-i/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [put-boxes-into-the-warehouse-i](https://leetcode.cn/problems/put-boxes-into-the-warehouse-i/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,3,4,1]\\n[5,3,3,4,1]', '[1,2,2,3,4]\\n[3,4,1,2]', '[1,2,3]\\n[1,2,3,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:\n",
    "        mn = inf\n",
    "        n = len(warehouse)\n",
    "        for i in range(n):\n",
    "            mn = min(mn, warehouse[i])\n",
    "            warehouse[i] = mn\n",
    "        boxes.sort(reverse=True)\n",
    "        ans = 0\n",
    "        while boxes and warehouse:\n",
    "            if boxes[-1] <= warehouse[-1]:\n",
    "                boxes.pop()\n",
    "                ans += 1\n",
    "            warehouse.pop()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:\n",
    "        s = warehouse[0]\n",
    "        for i in range(1, len(warehouse)):\n",
    "            if warehouse[i] > s:\n",
    "                warehouse[i] = s\n",
    "            s = min(s, warehouse[i])\n",
    "        boxes.sort()\n",
    "        n = len(boxes)\n",
    "        i = ans = 0\n",
    "        while i < n:\n",
    "            while warehouse and warehouse[-1] < boxes[i]:\n",
    "                warehouse.pop()\n",
    "            if not warehouse:\n",
    "                break\n",
    "            warehouse.pop()\n",
    "            ans += 1\n",
    "            i += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 动态规划+堆（优先队列）\n",
    "    # https://leetcode.cn/problems/put-boxes-into-the-warehouse-i/solutions/2392550/ba-xiang-zi-fang-jin-cang-ku-li-i-by-lee-kpx5/\n",
    "    def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:\n",
    "        n = len(warehouse)\n",
    "        for i in range(1, n):\n",
    "            warehouse[i] = warehouse[i-1] if warehouse[i-1] < warehouse[i] else warehouse[i]\n",
    "\n",
    "        heapq.heapify(boxes)\n",
    "        ans = 0\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if boxes and boxes[0] <= warehouse[i]:\n",
    "                ans += 1\n",
    "                heapq.heappop(boxes)\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:\n",
    "        boxes.sort()\n",
    "        for i in range(1, len(warehouse)):\n",
    "            warehouse[i] = min(warehouse[i - 1], warehouse[i])\n",
    "        res = 0\n",
    "        right = len(warehouse) - 1\n",
    "        i = 0\n",
    "        while right >= 0 and res < len(boxes):\n",
    "            if boxes[i] <= warehouse[right]:\n",
    "                res += 1\n",
    "                i += 1\n",
    "                right -= 1\n",
    "            else:\n",
    "                right -= 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:\n",
    "        m, n = len(boxes), len(warehouse)\n",
    "        boxes.sort()\n",
    "        ans = 0\n",
    "        for i in range(1, n):\n",
    "            warehouse[i] = min(warehouse[i], warehouse[i - 1])\n",
    "        for h in reversed(warehouse):\n",
    "            if ans < m and h >= boxes[ans]:\n",
    "                ans += 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:\n",
    "        n = len(warehouse)\n",
    "\n",
    "        min_so_far = math.inf\n",
    "        for i in range(n):\n",
    "            warehouse[i] = min(min_so_far, warehouse[i])\n",
    "            min_so_far = min(min_so_far, warehouse[i])\n",
    "\n",
    "        boxes = sorted(boxes)\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if res < len(boxes) and boxes[res] <= warehouse[i]:\n",
    "                res += 1\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:\n",
    "       # 对仓库房间的高度进行预处理，以获得可用高度\n",
    "       for i in range(1, len(warehouse)):\n",
    "           warehouse[i] = min(warehouse[i - 1], warehouse[i])\n",
    "\n",
    "       # 从最小到最大遍历方框\n",
    "       boxes.sort()\n",
    "\n",
    "       count = 0\n",
    "\n",
    "       for room in reversed(warehouse):\n",
    "           # 清点能放进当前库房的箱子\n",
    "           if count < len(boxes) and boxes[count] <= room:\n",
    "               count += 1\n",
    "\n",
    "       return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBoxesInWarehouse(self, B: List[int], H: List[int]) -> int:\n",
    "        lo = inf\n",
    "        for i, h in enumerate(H):\n",
    "            if lo > h: lo = h\n",
    "            H[i] = lo\n",
    "        \n",
    "        B.sort()\n",
    "        i, m = 0, len(B)\n",
    "        for h in reversed(H):\n",
    "            if i < m and B[i] <= h:\n",
    "                i += 1\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:\n",
    "        i, j = len(boxes) - 1, len(warehouse) - 1\n",
    "        boxes.sort(reverse=True)\n",
    "        ans = 0\n",
    "        mn = warehouse[0]\n",
    "        for idx in range(len(warehouse)):\n",
    "            if mn < warehouse[idx]:\n",
    "                warehouse[idx] = mn\n",
    "            elif mn > warehouse[idx]:\n",
    "                mn = warehouse[idx]\n",
    "\n",
    "        while i >= 0 and j >= 0:\n",
    "            if boxes[i] <= warehouse[j]:\n",
    "                ans += 1\n",
    "                i -= 1\n",
    "                j -= 1\n",
    "            elif boxes[i] > warehouse[j]:\n",
    "                j -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:\n",
    "        n = len(warehouse)\n",
    "\n",
    "        min_so_far = math.inf\n",
    "        for i in range(n):\n",
    "            warehouse[i] = min(min_so_far, warehouse[i])\n",
    "            min_so_far = min(min_so_far, warehouse[i])\n",
    "\n",
    "        boxes = SortedList(boxes)\n",
    "        \n",
    "        res = 0\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            limit = warehouse[i]\n",
    "            pos = boxes.bisect_right(limit)\n",
    "            if pos != 0:\n",
    "                res += 1\n",
    "                boxes.remove(boxes[pos - 1])\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBoxesInWarehouse(self, B: List[int], H: List[int]) -> int:\n",
    "        lo = inf\n",
    "        for i, h in enumerate(H):\n",
    "            if lo > h: lo = h\n",
    "            H[i] = lo\n",
    "        \n",
    "        B.sort()\n",
    "        i, m = 0, len(B)\n",
    "        for h in H[::-1]:\n",
    "            if i < m and B[i] <= h:\n",
    "                i += 1\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:\n",
    "        warehouse = list(accumulate(warehouse, func=min))\n",
    "        # print(warehouse)\n",
    "        boxes.sort()\n",
    "        box_id = ans = 0\n",
    "        n = len(boxes)\n",
    "        for height in reversed(warehouse):\n",
    "            if box_id == n:\n",
    "                return n\n",
    "            if height >= boxes[box_id]:\n",
    "                box_id += 1\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:\n",
    "        box_len = len(boxes)\n",
    "        house_len = len(warehouse)\n",
    "        ave_house = [0 for _ in range(house_len)]\n",
    "        ave_h = float('inf')\n",
    "        for i in range(house_len):\n",
    "            if ave_h > warehouse[i]:\n",
    "                ave_h = warehouse[i]\n",
    "            ave_house[i] = ave_h\n",
    "        boxes.sort()\n",
    "        b_i = 0\n",
    "        for i in range(house_len - 1, -1, -1):\n",
    "            if boxes[b_i] <= ave_house[i]:\n",
    "                b_i += 1\n",
    "            if b_i >= box_len:\n",
    "                break\n",
    "            else:\n",
    "                continue\n",
    "        return b_i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:\n",
    "        m, n = len(boxes), len(warehouse)\n",
    "        boxes.sort(reverse=True)\n",
    "        if m > n:\n",
    "            boxes = boxes[m - n:]\n",
    "            m = n \n",
    "        low, high = 0, m \n",
    "\n",
    "        def check(x):\n",
    "            for i in range(x):\n",
    "                if boxes[i + m - x] > warehouse[i]:\n",
    "                    return False\n",
    "            return True \n",
    "        \n",
    "        ans = 0\n",
    "        while low <= high:\n",
    "            mid = (low + high) // 2\n",
    "            if check(mid):\n",
    "                ans = mid \n",
    "                low = mid + 1\n",
    "            else:\n",
    "                high = mid - 1\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:\n",
    "\n",
    "       i = 0\n",
    "       count = 0\n",
    "       boxes.sort(reverse = True)\n",
    "\n",
    "       for room in warehouse:\n",
    "           # 从最小到最大遍历方框\n",
    "           # 丢弃不适合当前仓库的箱子\n",
    "           while i < len(boxes) and boxes[i] > room:\n",
    "               i += 1\n",
    "           if i == len(boxes):\n",
    "               return count\n",
    "           count += 1\n",
    "           i += 1\n",
    "\n",
    "       return count\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
